package tree.Huffman.decodingAndCoding;

import com.sun.source.tree.NewArrayTree;

import javax.imageio.plugins.tiff.GeoTIFFTagSet;
import java.sql.Array;
import java.util.*;

/**
 * 目前只支持纯字母,无空格的编码与解码
 */
public class HuffmanTree_DataCompense {
    private List<Node> list = new ArrayList<>();
    private Map<Character, String> encodingTable = new HashMap<>();

    /**
     * 统计sentence中各个字符出现的次数
     *
     * @param sentence
     * @return 以Node节点的列表形式存储, weight表示权重, value表示字符
     */
    public List weightCal(String sentence) {
        Set<Character> keySet;
        HashMap<Character, Integer> map = new HashMap<>();
        String sentence1 = sentence.trim();
        char[] chars = sentence1.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            if (map.containsKey(chars[i])) {
                map.put(chars[i], map.get(chars[i]).intValue() + 1);
            } else {
                map.put(chars[i], 1);
            }
        }
        keySet = map.keySet();
        Node node;
        for (char ch : keySet) {
            node = new Node(ch, map.get(ch));
            list.add(node);
        }
        Collections.sort(list);
        return list;
    }

    /**
     * 创建哈夫曼编码数,以获得最佳编码
     *
     * @param list
     * @return
     */
    public Node createEncodingTree(List<Node> list) {
        Node lnode;
        Node rnode;
        Node temp;
        Node root;
        while (list.size() > 1) {
            lnode = list.remove(0);
            rnode = list.remove(0);
            temp = new Node('1', lnode.weight + rnode.weight);
            temp.rigth = rnode;
            temp.left = lnode;
            list.add(temp);
            Collections.sort(list);
        }
        root = list.remove(0);
        return root;
    }

    /**
     * 生成编码,将数据保存到encodingTable中
     *
     * @param root
     * @param builder
     */
    public void encoding(Node root, StringBuilder builder) {
        if (root == null) {
            System.out.println("空编码树");
            return;
        }

        Node temp = root;
        if (temp.left == null && temp.rigth == null) {
            //叶子节点
            encodingTable.put(temp.value, builder.toString());
            //builder.deleteCharAt(builder.length()-1);
            return;
        }
        if (temp.left != null) {
            builder.append("0");
            encoding(temp.left, builder);
            builder.deleteCharAt(builder.length() - 1);
        }
        if (temp.rigth != null) {
            builder.append("1");
            encoding(temp.rigth, builder);
            builder.deleteCharAt(builder.length() - 1);
        }

    }

    /**
     * 生成指定文字的二进制编码
     */
    public String toencoding(String sentence) {
        char[] chars = sentence.toCharArray();
        StringBuilder code = new StringBuilder();
        //获取编码表table
        List list = weightCal(sentence);
        Node root = createEncodingTree(list);
        encoding(root, new StringBuilder());
        Map<Character, String> table = getEncodingTable();
        Set<Character> keySet = table.keySet();
        //正式开始编码
        for (int i = 0; i < chars.length; i++) {
            for (char key : keySet) {
                if (chars[i] == key) {
                    code.append(table.get(key));
                }
            }
        }
        return code.toString();

    }

    /**
     * 将一段二进制编码,解码为相应的字符串
     *
     * @return
     */
    public String decoding(String code1) {
        char[] codes = code1.toCharArray();
        StringBuilder currentCode = new StringBuilder();
        StringBuilder builder = new StringBuilder();
        Set<Character> keySet = encodingTable.keySet();
        boolean flag;
        for (int i = 0; i < codes.length; i++) {

            currentCode.append(codes[i]);
            flag=false;
            if (encodingTable.containsValue(currentCode.toString())) {
                //包含当前编码
                for (char key : keySet) {
                    //遍历key集合找到值为currentcode的key
                    String code = encodingTable.get(key);
                    if (code.contains(currentCode.toString())) {
                        builder.append(key);
                        flag = true;
                    }
                }
            }
            if (!flag) {
                //没有匹配   //空格
                if (currentCode.toString().equals(" "))
                    builder.append(" ");
            } else {
                //成功匹配
                currentCode.delete(0,currentCode.length());
            }
        }

        return builder.toString();
    }


    public Map<Character, String> getEncodingTable() {
        return encodingTable;
    }
}

class Node implements Comparable {
    char value;
    int weight;
    Node left;
    Node rigth;

    public Node(char value, int weight) {
        this.value = value;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Object o) {
        Node temp = (Node) o;

        return this.weight - temp.weight;
    }
}
